package 递归回溯;

import com.alibaba.fastjson.JSON;

import java.rmi.dgc.DGC;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

public class No401二进制手表 {

    /**
     * 二进制手表顶部有 4 个 LED 代表 小时（0-11），底部的 6 个 LED 代表 分钟（0-59）。
     * 每个 LED 代表一个 0 或 1，最低位在右侧。
     * 例如，上面的二进制手表读取 “3:25”。
     * 给定一个非负整数 n 代表当前 LED 亮着的数量，返回所有可能的时间。
     *
     * 示例：
     * 输入: n = 1
     * 返回: ["1:00", "2:00", "4:00", "8:00", "0:01", "0:02", "0:04", "0:08", "0:16", "0:32"]
     */

    private int[] hourArr=new int[]{1,2,4,8};
    private int[] minArr=new int[]{1,2,4,8,16,32};
    private List<String> list=new ArrayList<>();
    int count;

    /**
     * 还有更Good的方法
     * 我们只需计算小时[1~12]和分钟[1~60]两者分别由多少的1组成,等于num就开始验算并加入结果集
     */
    public List<String> readBinaryWatch(int num) {
        dg(0,0,num,0,new ArrayDeque<>());
        return list;
    }

    private void dg(int min, int hour,int n,int start,Deque<Integer> path){

        if(hour>11||min>59)
            return;
        if(path.size()>n)
            return;
        if(path.size()==n){
            int meHour=0;
            int meMin=0;
            for (Integer i : path) {
                if(i>=60){
                    meHour+=i/60;
                }else{
                    meMin+=i;
                }
            }
            StringBuilder sb=new StringBuilder();
            sb.append(meHour).append(":");
            if(meMin<10){
                sb.append("0").append(meMin);
            }else{
                sb.append(meMin);
            }
            list.add(sb.toString());
            return;
        }

        /**
         * 重点:回溯的for优化就用代数法优化~
         * 怎么个优化法呢?
         * -[需要的个数-已经放进的数]+1;
         * 因为你将数字带进去就能推理出来,例子:
         * 刚开始 n为2,length[<10]这时只需要遍历到8就可以了,所以就是[<9],最大就是8;
         * 以开始状态带入:10-(2-0)+1=9 [<9]符合代入式
         */
        for (int i = start; i < minArr.length+hourArr.length-(n-path.size())+1; i++) {
            count++;
            if(i<4){
                //加小时
                path.addLast(hourArr[i]*60);
                dg(min,hour+hourArr[i],n,i+1,path);
                path.removeLast();
            }else{
                //加分钟
                path.addLast(minArr[i-4]);
                dg(min+minArr[i-4],hour,n,i+1,path);
                path.removeLast();
            }
        }

    }

    public List<String> readBinaryWatchGood(int num){

        for (int i = 0; i < 12; i++) {
            for (int j = 0; j < 60; j++) {
                int i1 = Integer.bitCount(i);
                int i2 = Integer.bitCount(j);
                if(i1+i2==num){
                    StringBuilder sb=new StringBuilder();
                    sb.append(i).append(":");
                    if(j<10){
                        sb.append("0").append(j);
                    }else{
                        sb.append(j);
                    }
                   list.add(sb.toString());
                }
            }
        }
        return list;
    }
    
    public static void main(String[] args) {
        No401二进制手表 n=new No401二进制手表();
        List<String> list = n.readBinaryWatch(5);
        System.out.println(JSON.toJSONString(list));
        System.out.println(n.count);
    }

}
